EC Final 2018 vp 记录
题面太长了（），被吓走了…… 只做下面几题！
$A$
题面长差评（你被 300iq contest 惯坏了！）
好题！
删是单个删，一条边价值算多次
$w$ 很小。
算一条边或一种权值的边出现次数不好做。
$ans = \sum_e w(e) = \sum\limits_{i = 1}^{30} \sum_e [w(e) \geq i]$
上面这个的意义是，加好 $< i$ 的边后，形成的连通块数 $- 1$。
这个高明！不用考虑最小化边数最小化权值和什么的，直接简单维护连通性即可！很好做。
拆点并查集，当前若 $u + n$ 和 $v + n$ 连通则 $u’$ 和 $v’$ 连通，不用加边 $(u’, v’)$；否则 $u’$ 和 $v’$ 也应该连通（不用最小化边数以最小化权值和），要加边 $(u’, v’)$
实现细节：对于 $(u, v)$，要连续合并好几列的 $(u, v)$，而我们真正有机会考虑 $(u’, v’)$ 只在一开始加入，和 $u + n$ 和 $v + n$ 连通时停止加边。于是维护加边情况的差分。
我们只需要知道新连通的 $(u + n, v + n)$ 数量，而不需要知道具体是哪些对。
每条边只会被加一次 ban 一次，复杂度 $O(30(m + e))$。
$B$
大小为 $n$ 的本质不同析合树计数？
$dp_{i, j}$ 表示长度为 $i$ 的序列，划分成 $j$ 个连续子段的本质不同析合树个数, $f_n$ 表示大小为 $n$ 的本质不同析合树个数。
根是合点：合点儿子数至少为 $2$，只需要把 $i$ 划分成至少 $2$ 个子段然后必然存在一种合法方案给它们拼起来
根是析点：析点儿子数至少为 $4$，只需要把 $i$ 划分成至少 $4$ 个子段然后必然存在一种合法方案给它们拼起来
$f_i = \sum\limits_{k \geq 2, \sum a_k = i} \prod\limits_{j = 1}^k f(a_k) + \sum\limits_{k \geq 4, \sum a_k = i} \prod\limits_{j = 1}^k f(a_k)$
维护一下子段个数 $= 2$、$= 3$、$\geq 4$ 三类即可, $O(n^2)$
$C$
$\mu$……？所有完全平方数的倍数一定为 $0$！
暴枚显然不行……
$200$ 以内的质完全平方数有 $4$ $9$ $25$ $49$ $121$ $169$
考虑 $a^k \equiv p + i \pmod{lcm(4, 9, 25, 49) = 44100}$（不取 $121$、$169$ 是为了让 $lcm$ 大小刚好，其余的位置可以后面 check）
枚举 $p \mod 44100$ 的余数，在合法的余数处枚举倍数并 $check$。合法的余数很少，完全跑不满。可以加一些剪枝和卡时。
$E$
神仙题。
当 $hp = 1$ 且接下来俩都是 $-1$ 就死了。
分开做，最后暴力合并。
倒着 dp，状态为当前后缀和，碰到一个 $-1$ 的时候，大于 $0$ 的后缀和要清零。
不懂的话，画折线图。
非常神奇，这样可以保证每对 $-1$ 前的前缀和 $> 0$。$F \times F$ 显然，$F \times G$ 呢？后缀与前缀的折线关于 $x$ 轴对称，小于 $0$ 的后缀和被延续下来，其实就是前缀和 $> 0$。
特殊情况是，如果最终结果是 $0 + 0$，中途不能小于 $0$。
$G$
很神仙的构造题，先咕了
$H$
咕咕咕
$J$
啊这…… 模拟赛搬过的题
lcp，反建 SAM。
考虑合并，$ans = \min( lans x + (1 - x) h, rans (1 - x) + x h )$，$X$ 形函数下表面，相交处即相等处最大。所以子树答案相等时答案最大。比例分配一下。
和某 THUPC2020-切糕 很像。
$K$
询问有多少区间存在子序列可以凑出 $k$ 级。
$2^k$ 个 $w$ 级可以凑一个 $w + k$ 级
$k$ 只有 $log$！然而你还是不知道怎么做。
以每个位置为左端点，合成某个 $k$ 的子区间数量只要求出对应的最小右端点就行了。
所以考虑 dp：$f[i, j]$ 表示 $i$ 位置要合成 $j$ 至少往后延伸多少距离
$f[i, j] = \min( f[f[i, j - 1] + 1, j - 1], nxt[i, j] )$
$nxt[i, j]$ 表示 $i$ 后第一个 $j$
对于询问 $(l, r, k)$，二分出满足 $f_{p, k} \leq r$ 的最大 $p$，$ans = \sum\limits_{i \in [l, p]} (r + 1 - f[i, k]) = (p - l + 1) * (r + 1) - \sum\limits_{i \in [l, p]} f[i, k]$
我们需要知道 $Q$ 个区间的 $\sum f[, k]$
对于每个 $k$，$f[i, k]$ 的位置单调不减，即是若干个连续段。
大胆猜测对于所有的 $k$，$f[i, k]$ 形成的连续段数之和是 $O(nlogn)$ 级别，因为每次新生成的段数在倍增作用下只会影响 $log$ 层
于是挨段挨段二分连续段边界即可，每层会在上一层的基础上加入一些 $nxt[i, j]$ 代表的端点形成的新段。$O(nlog^2n)$